A polygon mesh is a collection of vertices, edges and faces that defines the shape of a polyhedral object for 3D computer graphics and solid modeling. The faces usually consist of triangles, quadrilaterals or other simple convex polygons, since this simplifies rendering, but may also be composed of more general concave polygons, or polygons with holes. Many popular schemes employ triangular meshes such as strips of triangles (each triangle sharing one edge with one neighbor and another with the next) and/or triangle fans (a set of connected triangles sharing one central vertex). FIG. 1 shows a perspective view of an object 101 with a triangle mesh on its surface. (In this figure, two of the triangles (103), along with their normals N1 and N2, and a view source are shown. for simplicity, the rest of the mesh is not included.)
Silhouette edge detection is used in 3D graphics engines for a number of algorithms including stylized rendering for technical illustrations and shadow determination. Given a position in space (view source, e.g., a person's eyes or a camera), a silhouette edge is an edge shared by two triangles where one triangle faces the view source (N1) and the other faces away (n2). Traditional silhouette edge detection techniques compare the normal of each face, relative to the view source, with the normals of each of neighboring faces. For example, a typical way of silhouette edge detection involves taking the dot product of face normals and the view direction and checking where they change sign. When the sign changes, the edge common to the two compared faces is part of the silhouette. Unfortunately, this approach can be exhaustive, consuming excessive processing and memory resources. Accordingly, new approaches are desired.